package com.hermeneute.fsa;

import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class FSTTransposedAutomaton {
    HashSet markS;
    Hashtable memory;
    FSTPivotStack pivotStack;
    HashSet eventsByState[];
    FSTStateItem stateIndex [];
    LinkedList classIndex [];
    FSTAutomaton ia;
    FSTAutomaton result;
    int classPos;
    int classInterCard[];
    int classInterMark[];
    int newClass [];
    int marker1 [];
    int markerV;
    int stateList[];
    int statesToProcess;
    int classToprocess;
    int collisions;
    int totalit;
    boolean voidAutomaton;
    HashSet<Integer> mark;
    
    ListIterator getListIterator(LinkedList l) {
	if (l == null) {
	    return null;
	} else {
	    return l.listIterator();
	}
    }
    
    Iterator getIteratorSet(HashSet s) {
	if (s == null) {
	    return null;
	} else {
	    return s.iterator();
	}
    }

    void pushPivots(int classn) {
	FSTEvent e;
	FSTStateItem si;
	int i;
	
	for (ListIterator st = getListIterator(classIndex[classn]);
	     st != null && st.hasNext();) {
	    if (st == null) {System.err.println("Clang");System.exit(0);}
	    si = (FSTStateItem)st.next();
	    i = si.getState();
	    for(Iterator el = getIteratorSet(eventsByState[i]);
		el != null&&el.hasNext();) {
		e = (FSTEvent) el.next();
		pivotStack.push(new FSTPivot(classn,e));
	    }
	}
    }

    void pushPivots(int classa,int classb) {
	FSTEvent e;
	FSTStateItem si;
	int i;
	
	for (ListIterator st = getListIterator(classIndex[classa]);
	     st != null && st.hasNext();){
	    si = (FSTStateItem)st.next();
	    i = si.getState();
	    for(Iterator el = getIteratorSet(eventsByState[i]);
		el != null&&el.hasNext();) {
		e = (FSTEvent) el.next();
		pivotStack.push(new FSTPivot(classa,e));
	    }
	}
	
	for (ListIterator st = getListIterator(classIndex[classb]);
	     st != null && st.hasNext();){
	    si = (FSTStateItem)st.next();
	    i = si.getState();
	    for(Iterator el = getIteratorSet(eventsByState[i]);
		el != null&&el.hasNext();) {
		e = (FSTEvent) el.next();
		if (pivotStack.exists(classa,e)) {
		    pivotStack.push(new FSTPivot(classb,e));
		}
	    }
	}
    }
    
    void cardInter(FSTPivot p) {
	FSTStateItem si;
	HashSet urlu;
	int i;
	
	for (ListIterator st = getListIterator(classIndex[p.getNumber()]);
	     st != null && st.hasNext();) {
	    si = (FSTStateItem)st.next();
	    urlu = 
		(HashSet)memory.get(new FSTPivot(si.getState(),p.getEvent()));
	    if(urlu != null) {
		for (Iterator it = urlu.iterator(); 
		     it.hasNext();) {
		    i = ((Integer)it.next()).intValue();
		    totalit++;
		    classInterMark[i] = 0;
		    classInterCard[stateIndex[i].getStateClass()] = 
			- classIndex[stateIndex[i].getStateClass()].size();
		}
	    }
	}
	
	for (ListIterator st = getListIterator(classIndex[p.getNumber()]);
	     st != null && st.hasNext();) {
	    si = (FSTStateItem)st.next();
	    urlu = 
		(HashSet)memory.get(new FSTPivot(si.getState(),p.getEvent()));
	    if(urlu != null) {
		for (Iterator it = urlu.iterator(); 
		     it.hasNext();) {
		    i = ((Integer)it.next()).intValue();
		    totalit++;
		    if(classInterMark[i] == 0) {
			classInterMark[i] = 1;
			classInterCard[stateIndex[i].getStateClass()]++;
		    }
		}
	    }
	}
	statesToProcess = 0;
      
	for (ListIterator st = getListIterator(classIndex[p.getNumber()]);
	     st != null && st.hasNext();) {
	    si = (FSTStateItem)st.next();
	    urlu = 
		(HashSet)memory.get(new FSTPivot(si.getState(),p.getEvent()));
	    if(urlu != null) {
		for (Iterator it = urlu.iterator(); 
		     it.hasNext();) {
		    i = ((Integer)it.next()).intValue();
		    totalit++;
		    if(classInterCard[stateIndex[i].getStateClass()]<0){
			if (marker1[i] != markerV) {
			    marker1[i] = markerV;
			    stateList[statesToProcess++] = i;
			}
			newClass[stateIndex[i].getStateClass()] = 0;
		    }
		}
	    }
	}
    }    
    
    void getNewClasses (FSTPivot p) {
	int s;
	
	//System.out.println("Before cardInter");
	cardInter(p);
	//System.out.println("After cardInter");
	
	classToprocess = 0;
	for (int i = 0;i < statesToProcess;i++) {
	    s = stateList[i];
	    totalit++;
	    if(classInterCard[stateIndex[s].getStateClass()]<0 &&
	       newClass[stateIndex[s].getStateClass()] == 0){
		classInterMark[classToprocess++] = 
		    stateIndex[s].getStateClass();
		newClass[stateIndex[s].getStateClass()] = 
		    classPos;
	    classIndex[classPos] = new LinkedList();
	    classPos++;
	    }
	}
	
	//System.out.println("Before swap "+statesToProcess);
	for (int i = 0;i < statesToProcess;i++) {
	    s = stateList[i];
	    totalit++;
	    if (stateIndex[s].getStateClass() >= classPos) {
		System.err.println("Clong!!!");
		System.exit(0);
	    }
	    
	    if(classInterCard[stateIndex[s].getStateClass()] < 0) {
		FSTStateItem tss = stateIndex[s];
		LinkedList tcl = classIndex [tss.getStateClass()];
		LinkedList tncl = classIndex[newClass[tss.getStateClass()]];
		tcl.remove(new FSTStateItem(tss.getState()));
		tncl.add(new FSTStateItem(tss.getState())); 
		tss.setStateClass(newClass[tss.getStateClass()]);
	    }
	}
	//System.out.println("After swap");

	//printf(")\n");
	
	for (int i = 0; i < classToprocess; i++) {
	    LinkedList tcl = classIndex [classInterMark[i]];
	    LinkedList tncl = classIndex[newClass[classInterMark[i]]];
	    int nc = newClass[classInterMark[i]];
	    int oc = classInterMark[i];
	    
	    if (tncl.size() <= tcl.size()) {
		//fprintf (stderr,"menganito %d\n",nc);
		pushPivots(nc);
		//pushPivots(oc);
	    } else {
		//fprintf (stderr,"fulanito %d %d\n",oc,nc);
		//pushPivots(oc,nc); 
		pushPivots(oc);
		pushPivots(nc);
	    }
	    //fprintf (stderr,"Alla\n");
	}
    }
    
    
    void transpose (int st) {
	int s;
	FSTEvent e;
	HashSet ts;
    
	if (!mark.contains(new Integer(st)))  {
	    mark.add(new Integer(st));
	    //FSTTransitionIterator getTransitions(int st)
	    for(FSTTransitionIterator it = ia.getTransitions(st);
		it.hasNext();) {
		it.next();
		e = it.getEvent ();
		s = it.getState ();
		ts = (HashSet)memory.get(new FSTPivot(s,e));
		if (ts != null) {
		    ts.add(new Integer(st));		
		} else {
		    if (eventsByState[s] != null) {
			eventsByState[s].add(e);
		    } else {
			eventsByState[s] = new HashSet();
			eventsByState[s].add(e);
		    }
		    
		    memory.put(new FSTPivot(s,e),new HashSet());
		    ((HashSet)memory.get(new FSTPivot(s,e))).
			add(new Integer(st));
		}
	    
		transpose(s);
	    }
	}
    }

    void initPartition() throws Exception {
	int i;
	FSTStateItem tmp;
	stateIndex = new FSTStateItem [ia.getFirstFreeState ()+2];
	classIndex = new LinkedList [ia.getFirstFreeState ()+2];
	classInterCard = new int [ia.getFirstFreeState ()+2];
	classInterMark = new int [ia.getFirstFreeState ()+2];
	newClass = new int [ia.getFirstFreeState ()+2];
	stateList = new int [ia.getFirstFreeState ()+2];
	marker1 = new int [ia.getFirstFreeState ()+2];
	FSTStateItem si;
	markStates(ia.getStart());
	
	for(i = 0; i < ia.getFirstFreeState ()+2;i++) {
	    stateIndex[i] = null;
	    classIndex[i] = null;
	    marker1[i] = 0;
	    stateList[i] = 0;
	    classInterMark[i] = 0;
	    classInterCard[i] = 0;
	    newClass[i] = 0;
	}
	classIndex[1] = new LinkedList();
	classIndex[2] = new LinkedList();
	classIndex[3] = new LinkedList();
	classPos = 4;
	voidAutomaton = true;
	for (int st = 1; st < ia.getFirstFreeState ()+2;st++) {
	    if(markS.contains(new Integer(st))) {
		tmp = new FSTStateItem(st);
		
		if(ia.isFinalState(st)) {
		    voidAutomaton = false;
		    tmp.setStateClass(2);
		    classIndex[2].add(tmp);
		} else if(ia.isSinkState(st)) {
		    tmp.setStateClass(3);
		    classIndex[3].add(tmp);
		} else {
		    tmp.setStateClass(1);
		    classIndex[1].add(tmp);
		}
		stateIndex[st] = tmp;
	    }
	}
	if (voidAutomaton) {
	    System.err.println("WARNING void automaton");
	    throw new Exception("Void Automaton in optimizer");
	}
	
	if (classIndex[3].size() == 0) {
	    classIndex[3] = null;
	    classPos--;
	}
	if (classIndex[1].size() == 0) {
	    classIndex[1] = classIndex[classPos-1];
	    classIndex[classPos-1] = null;
	    classPos--;
	    for (ListIterator st = getListIterator(classIndex[1]);
		 st != null && st.hasNext();) {
		si = (FSTStateItem)st.next();
		stateIndex[si.getState()].setStateClass(1);
	    }
	    if(classPos == 2)
		pushPivots(1);
	    else {
		pushPivots(1);
		pushPivots(2);
	    }
	} else{
	    pushPivots(1);
	    if(classIndex[3] != null)
	      pushPivots(3);
	    pushPivots(2);
	}
    }

    void partitionRefinement() throws Exception {
	int it = 0;
	FSTPivot tp;
	markerV = 1;
	if (voidAutomaton) {
	    System.err.println("WARNING void automaton");
	    throw new Exception("Void Automaton in optimizer");
	}
	
	while(!pivotStack.isEmpty()) {
	    //System.out.println("Iteration refinement "+it);
	    it++;
	    tp = pivotStack.pop();
	    getNewClasses(tp);
	    markerV++;
	}
    }
    

  void markStates (int st) {
    FSTEvent e;
    
    if (!markS.contains( new Integer(st))) {
	markS.add(new Integer(st));
	for(FSTTransitionIterator it = ia.getTransitions(st);
	    it.hasNext();) {
	    it.next();
	    if (it.getState() != 0)
		markStates(it.getState ());
	}
    }
  }
  

  void buildResult() throws Exception{
      int i;
      int sinkClass;
      int startClass;
      int tmp;
      int reachedPos;
      FSTStateItem si;

      sinkClass = 0;
      FSTEvent myany = new FSTEvent(FSTEvent.Any,FSTEvent.Any);
    

    if (result == null)
	result = new FSTAutomaton ();
    result.setStart (1);
    if (voidAutomaton) {
    	throw new Exception("Void Automaton in optimizer");
	//exit(0);
    }

    startClass = stateIndex[ia.getStart()].getStateClass();
    //fprintf (stderr,"Changing start\n");
    if (startClass != 1) {
	LinkedList tmpClass;
	tmpClass = classIndex[startClass];
	classIndex[startClass] = classIndex[1];
	classIndex[1] = tmpClass;

	for (ListIterator st = getListIterator(classIndex[1]);
	     st != null && st.hasNext();) {
	    si = (FSTStateItem)st.next();
	    stateIndex[si.getState()].setStateClass(1);
	}
	for (ListIterator st = getListIterator(classIndex[startClass]);
	     st != null && st.hasNext();) {
	    si = (FSTStateItem)st.next();
	    stateIndex[si.getState()].setStateClass(startClass);
	}
    }
    sinkClass = 0;
    for (i=1; i < ia.getFirstFreeState ()+2;i++) {	
	if (markS.contains(new Integer (i)) && ia.isSinkState(i)) {
	    sinkClass = stateIndex[i].getStateClass();
	  }
      }
    if (sinkClass != 0 && sinkClass != classPos - 1) {
	LinkedList tmpClass;
	tmpClass = classIndex[sinkClass];
	classIndex[sinkClass] = classIndex[classPos-1];
	classIndex[classPos-1] = tmpClass;
	for (ListIterator st = getListIterator(classIndex[sinkClass]);
	     st != null && st.hasNext();) {
	    si = (FSTStateItem)st.next();
	    stateIndex[si.getState()].setStateClass(sinkClass);
	}

	for (ListIterator st = getListIterator(classIndex[classPos-1]);
	     st != null && st.hasNext();) {
	    si = (FSTStateItem)st.next();
	    stateIndex[si.getState()].setStateClass(classPos-1);
	}
	sinkClass = classPos - 1;
    }

    for (i=1; i < ia.getFirstFreeState ()+2;i++) {
	if (stateIndex[i] != null)
	    for(FSTTransitionIterator it = ia.getTransitions(i);
		it.hasNext();) {
		it.next();
		if (it.getState() != 0)
		    markStates(it.getState ());
		int tmpstate = result.
		nextState(stateIndex[i].getStateClass(),it.getEvent());
	      if (it.getState() != 0)  {
		  result.
		      addTransition(stateIndex[i].getStateClass(),
				       it.getEvent(),
				       stateIndex[it.getState()].getStateClass());
		}
	    }
      }
    //result.print();
    for (i=1; i < ia.getFirstFreeState () + 2;i++)
      {	
	if (markS.contains(new Integer(i)) && ia.isFinalState (i))
	  {
	    result.insertFinalState (stateIndex[i].getStateClass());
	  }
      }

    result.setFirstFreeState(classPos+1);
    //fprintf(stderr,"Done %d states\n",classPos);
  }
  FSTTransposedAutomaton(FSTAutomaton a) throws Exception{
    pivotStack = new FSTPivotStack (a);
    memory = new Hashtable();
    markS = new HashSet();
    result = null;
    ia = a;
    collisions = 0;
    totalit = 0;
    //System.out.println(a.getFirstFreeState ());
    eventsByState = new HashSet [a.getFirstFreeState ()+2];
    for (int i = 0; i < a.getFirstFreeState ()+2;i++)
      {
	eventsByState[i] = null;
      }
    mark = new HashSet();
    transpose(a.getStart());
    mark.clear();
    initPartition();
    partitionRefinement();
    buildResult();
  }

    FSTAutomaton getResult() {
      return result;
    }
};

